class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def InsertLiast(self,head,val):
        temp=ListNode(val)
        while head.next!=None:
            head=head.next
        head.next=temp

    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1==None:return l2
        elif l2==None:return l1
        elif l1.val>=l2.val:
            l2.next=self.mergeTwoLists(l1,l2.next)
            return l2
        else:
            l1.next=self.mergeTwoLists(l1.next,l2)
            return l1
    def printList(self,head):
        while head!=None:
            print(head.val,end=' ')
            head=head.next
        print()
    def deleteNode(self, head: ListNode, val: int) -> ListNode:
        if head.val==val:return head.next
        x=head
        while head.next.val!=val:

            head=head.next
        head.next=head.next.next
        return x

if __name__ == '__main__':
    head1=ListNode(-1)
    head2=ListNode(-1)
    s=Solution()
    for i in range(0,10,2):
        s.InsertLiast(head1,i)
        s.InsertLiast(head2,i+1)
    print("开始合并链表")
    x=s.mergeTwoLists(head1,head2)
    s.printList(x)


